package com.learn.algorithm.exercises.nowcoder;

import java.util.HashSet;

/**
 * @author wangxing
 * @version 2020/7/10 16:25 Administrator
 */
public class PrimeProblem {
    static HashSet<Integer> prime = new HashSet<>();
    static HashSet<Integer> noPrime = new HashSet<>();

    static {
        prime.add(1);
        prime.add(2);
        prime.add(3);
        prime.add(5);
        noPrime.add(4);
    }

    /**
     * 有10^8个村庄排在一条公路上，依次编号为0~10^8-1，相邻村庄距离为1，其中有n个村庄居住着牛牛，居住着牛牛的村庄从小到大依次为a0~an-1，其中保证a0=0.
     * 现在需要建设车站，有两个要求必须被满足：
     * 1、每个有牛牛居住的村庄必须修建车站。
     * 2、相邻车站的距离必须为1或为某个质数。
     * 现给出n和a数组，求需要建设车站的最小数量。
     * 解题方式参考歌德巴克猜想:任一大于2的偶数都可写成两个素数之和。还有，任一大于5的整数都可写成三个质数之和。
     *
     * @param n 数组大小
     * @param a 数组信息
     * @return 建设最小数量
     */
    public int createTrain(int n, int[] a) {
        int num = 1;
        int temp;
        for (int i = 1; i < n; i++) {
            temp = a[i] - a[i - 1];
            if (isPrime(temp)) {
                num++;
            } else {
                if (temp % 2 == 0) {
                    num += 2;
                } else {
                    if (isPrime(temp - 2)) {
                        num += 2;
                    } else {
                        num += 3;
                    }

                }
            }
        }
        return num;
    }

    /**
     * 判断数字是否为素数/质数
     * （1）用2至number-1之间bai的所有数去整除number，如果有du一个能被整除，说明number是非素zhi数；除非所有的数都不能被整除，才说明number是素数。
     * （2）用2至number/2之间的所有数去整除number，如果有一个能被整除，说明number是非素数；除非所有的数都不能被整除，才说明number是素数。
     * （3）用2至number的平方根之间的所有数去整除number，如果有一个能被整除，说明number是非素数；除非所有的数都不能被整除，才说明number是素数。
     *
     * @param num 判定数
     * @return 是否为质数
     */
    public static boolean isPrime(int num) {
        if (prime.contains(num)) {
            return true;
        }
        if (noPrime.contains(num)) {
            return false;
        }
        if (num % 2 == 0) {
            noPrime.add(num);
            return false;
        }

        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                noPrime.add(num);
                return false;
            }
        }
        prime.add(num);
        return true;
    }
}
